package base.day07;

import base.day05.Node;

import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Stack;

/**
 * 描述：
 *      并查集
 * @author hl
 * @version 1.0
 * @date 2020/10/29 10:40
 */
public class Code_02_UnionFind {
    private Map<Node,Node> fatherMap;
    private Map<Node,Integer> sizeMap;

    public Code_02_UnionFind(List<Node> nodes) {
        makeSets(nodes);
    }
    private void makeSets(List<Node> nodes){
        this.fatherMap = new HashMap<>();
        this.sizeMap = new HashMap<>();
        for (Node node : nodes) {
            fatherMap.put(node, node);
            sizeMap.put(node, 1);
        }
    }
    public Node findHead(Node node){
        Node father = fatherMap.get(node);
        if (father != node) {
            father  = findHead(father);
        }
        fatherMap.put(node, father);
        return father;
    }
    public Node findHeadUnRecur(Node node){
        Stack<Node> stack = new Stack<>();
        Node cur = node;
        Node parent = fatherMap.get(cur);
        while(parent != cur){
            stack.add(node);
            cur = parent;
            parent = fatherMap.get(cur);
        }
        while(!stack.isEmpty()){
            fatherMap.put(stack.pop(),parent);
        }
        return parent;
    }
    public boolean isSameSet(Node a, Node b){
        return fatherMap.get(a) == fatherMap.get(b);
    }
    public void union(Node a, Node b){
        if (a == null || b == null) {
            return ;
        }
        Node ahead = findHead(a);
        Node bhead = findHead(b);
        if (sizeMap.get(a) <= sizeMap.get(b)) {
            fatherMap.put(ahead,bhead);
            sizeMap.put(b,sizeMap.get(a) + sizeMap.get(b));
        }else{
            fatherMap.put(bhead,ahead);
            sizeMap.put(a,sizeMap.get(a) + sizeMap.get(b));
        }
    }

}
